package util

import "math/rand"

type node struct {
	ch [2]*node
	priority int
	val int
}

func (n *node) GetVal() int {
	return n.val
}

const (
	LEFT = 0
	RIGHT = 1
	EQUAL = -1
)

func (o *node) cmp(b int) int {
	switch {
	case b < o.val:
		return LEFT
	case b > o.val:
		return RIGHT
	default:
		return EQUAL
	}
}

// d == LEFT, 左旋，o的位置被他的右孩子x替代
// d == RIGHT, 右旋，o的位置被他的左孩子替代，
func (o *node) rotate(d int) *node {
    x := o.ch[d^1]
    o.ch[d^1] = x.ch[d]
    x.ch[d] = o
    return x
}

type Treap struct {
	root *node
}

func (t *Treap) _put(o *node, val int) *node {
	if o == nil {
		return &node{priority: rand.Int(), val: val}
	}
	if d := o.cmp(val); d != EQUAL {
		o.ch[d] = t._put(o.ch[d], val)
		if o.ch[d].priority > o.priority {
			o = o.rotate(d ^ 1)
		}
	}
	return o
}

func (t *Treap) Put(val int) {
	t.root = t._put(t.root, val)
}

// 找一个节点，该节点的值大于等于val
// 如果找不到，返回nil
func (t *Treap) Lowerbound(val int) (lb *node) {
	for o := t.root; o != nil; {
		switch c := o.cmp(val); {
		case c == LEFT:
			lb = o
			o = o.ch[LEFT]
		case c == RIGHT:
			o = o.ch[RIGHT]
		default: // equal
			return o
		}
	}
	return
}